Minimum window subsequence

Time: O(SxT); Space: O(S); hard

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

If there is no such window in S that covers all characters in T, return the empty string “”. If there are multiple such minimum-length windows, return the one with the smallest starting index.

Constraints:

  • All the strings in the input will only contain lowercase letters.

  • The length of S will be in the range [1, 20000].

  • The length of T will be in the range [1, 100].

Example 1:

Input：S = “jmeqksfrsdcmsiwvaovztaqenprpvnbstl”，T = “u”

Output：””

Explanation:

  • unable to match

Example 2:

Input：S = “abcdebdde”， T = “bde”

Output：“bcde”

Explanation

  • “bcde” is the answer and “deb” is not a smaller window because the elements of T in the window must occur in order.

[1]:

class Solution1(object):
    """
    Time: O(S*T)
    Space: O(S)
    """
    def minWindow(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: str
        """
        lookup = [[None for _ in range(26)] for _ in range(len(S)+1)]
        find_char_next_pos = [None]*26

        for i in reversed(range(len(S))):
            find_char_next_pos[ord(S[i])-ord('a')] = i+1
            lookup[i] = list(find_char_next_pos)

        min_i, min_len = None, float("inf")

        for i in range(len(S)):
            if S[i] != T[0]:
                continue
            start = i
            for c in T:
                start = lookup[start][ord(c)-ord('a')]
                if start == None:
                    break
            else:
                if start-i < min_len:
                    min_i, min_len = i, start-i

        return S[min_i:min_i+min_len] if min_i is not None else ''

[2]:

s = Solution1()

S = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl"
T = "u"
assert s.minWindow(S, T) == ""

S = "abcdebdde"
T = "bde"
assert s.minWindow(S, T) == "bcde"

[6]:

class Solution2(object):
    def minWindow(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: str
        """
        dp = [[None for _ in range(len(S))] for _ in range(2)]

        for j, c in enumerate(S):
            if c == T[0]:
                dp[0][j] = j

        for i in range(1, len(T)):
            prev = None
            dp[i%2] = [None] * len(S)

            for j, c in enumerate(S):
                if prev is not None and c == T[i]:
                    dp[i % 2][j] = prev
                if dp[(i-1) % 2][j] is not None:
                    prev = dp[(i-1) % 2][j]

        start, end = 0, len(S)

        for j, i in enumerate(dp[(len(T)-1)%2]):
            if i and i >= 0 and j-i < end-start:
                start, end = i, j

        return S[start:end+1] if end < len(S) else ''

[8]:

s = Solution2()

S = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl"
T = "u"
assert s.minWindow(S, T) == ""

S = "abcdebdde"
T = "bde"
assert s.minWindow(S, T) == "bcde"